{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 1.      ,  0.018883, -0.300577],\n",
       "        [ 1.      ,  0.012003, -0.217283],\n",
       "        [ 1.      ,  0.134128, -0.195046],\n",
       "        [ 1.      ,  0.016241, -0.063215],\n",
       "        [ 1.      ,  0.126804,  0.001238]]),\n",
       " (50, 3))"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "#加载数据\n",
    "def load_data(file_name):\n",
    "    with open(file_name) as fr:\n",
    "        lines = fr.readlines()\n",
    "\n",
    "    data = np.empty((len(lines), 3), dtype=float)\n",
    "\n",
    "    for i in range(len(lines)):\n",
    "        line = lines[i].split('\\t')\n",
    "        data[i] = line\n",
    "\n",
    "    #根据y排序,主要是为了画图\n",
    "    argsort = data.argsort(axis=0)[:, 2]\n",
    "    data = data[argsort]\n",
    "\n",
    "    return data\n",
    "\n",
    "\n",
    "#剪枝的时候不能用训练数据\n",
    "data = load_data('简单数据_剪枝.txt')\n",
    "data[:5], data.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#定义常量\n",
    "N,M = data.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAATIklEQVR4nO3dYYxc11nG8efNekMmNHQjvKB6EmODikOKad0uIWIBJQHJSSiNMZVoG1qpQrIQKgpSMXUQIiA+eCtLUBCgykqjFhE1qhprKSTFirQJoS1Ou+4mcVLXKAQ19aSSN9BtabOl6/XLh9lx1uM7M3d2z7n33Dv/nxQpOzO+e64cPXPy3vecY+4uAEC6rih7AACA/ghqAEgcQQ0AiSOoASBxBDUAJG5LjItu3brVd+zYEePSAFBLJ0+efMXdJ7PeixLUO3bs0Pz8fIxLA0AtmdnXer1H6QMAEkdQA0DiCGoASBxBDQCJI6gBIHFRuj4AIKbZhZaOHD+jl5eWtW2ioYN7d2nfnmbZw4qGoAZQKbMLLd177JSWV1YlSa2lZd177JQk1TasKX0AqJQjx89cDOmO5ZVVHTl+pqQRxUdQA6iUl5eWh3q9DghqAJWybaIx1Ot1QFADqJSDe3epMT52yWuN8TEd3LurpBG16+bTM3PaeegRTc/MaXahFfT6PEwEkIS8nRyd11Lp+iji4SZBDaB0w4bdvj3NZDo8+j3cJKgB1EYRYdcRuge7iIeb1KgBlK6oTo7OzL21tCzXazP3zdSUi3i4SVADKF1RnRwxerCLeLhJUAMo3a03TMq6XovRyRFj5r5vT1OH9+9Wc6Ihk9ScaOjw/t1BSzbUqAGUanahpYdPtuTrXjNJv/G28A8Mt0001MoI5c3O3GM/3GRGDaBUWeUIl/T4VxeD/64Ue7DzYEYNoFRFPEhc3+nx+sa4rhq/QkuvrpTeg51X7qA2szFJ85Ja7v72eEMCMEpilSM6unu0l5ZX1Bgf01/+5luSD+iOYUof90g6HWsgAEZT7HJEHXbbyxXUZnadpF+VdH/c4QAYNbG7Juqw217e0sdHJP2hpGt6fcDMDkg6IEnbt2/f/MgAjIyYXROxSytFGDijNrO3Szrn7if7fc7dj7r7lLtPTU5OBhsgAGxGVTs91sszo56W9A4zu1PSVZJ+yMz+wd1/K+7QAGDzQu+2V8Z5jebugz/V+bDZLZL+YFDXx9TUlM/Pz29yaACQlu4OEqk9Ow9RUzezk+4+lfUeC14AIKeyOkiGWvDi7k9IeiLKSAAgcb06RVpLy5qemYtWDmFGDQA59eoUMSno1qndCGoAyCmrg8QkdT/pC10OIagBIKesxTm92jE44QUAStDdmpe1j3ZHyAU17J4HADlkHcD74ImXMmfUJnHCCwAUrde+2Vlc2aenbxRBDQA5DFNzbgbeR4SgBoAc+rXmrRdjHxGCGgBy6LW50903b496sK3Ew0QAyCX05k7DIKgBIKfYp433QukDABJHUANA4ghqAEgcQQ0AiSOoASBxBDUAJI6gBoDEEdQAkDiCGgASR1ADQOJYQg7URPfpI0XtQ4H4CGqgBrJOH7n32ClJYTewRzkIaqAAsWe7WaePdE7CJqirj6AGIitittvr9JGQJ2GjPDxMBCLrN9sNpdfpIyFPwkZ5CGogsiJmu71OHwl9JBTKQVADkRUx2923p6nD+3dHPxIK5aBGDUR2cO+uS2rUUpzZblmnjyA+ghqIrMyz9lAPBDVQAGa72Axq1ACQOGbUQI2xrLweCGqgplhWXh8DSx9mdpWZfdHMnjGz583sz4oYGIDNKWKhDYqRZ0b9f5Juc/fvmNm4pM+Z2Wfd/UTksQHYBJaV18fAGbW3fWftx/G1fzzqqABsGsvK6yNX14eZjZnZ05LOSXrM3Z/K+MwBM5s3s/nFxcXQ4wQwJJaV10euoHb3VXd/i6TrJN1kZj+d8Zmj7j7l7lOTk5OhxwlgSCwrr4+huj7cfcnMnpB0u6TnoowIQDAstKmHgUFtZpOSVtZCuiHpVyR9OPrIAPQVs0ea/uu05JlRv0HSJ8xsTO1Syafc/Z/jDgtAPzF7pPtdW7p0z5Jbb5jU419dJNAjM/fwDRxTU1M+Pz8f/LoA2qZn5tTKaLNrTjT0+UO3Rbn2tVeP63srFy7rzV6vMT5GHXyDzOyku09lvcdeH0AF9eqFzgrYUNf+5qsrfUNaYkFNLAQ1UEG9eqFN7dJFjGvnxYKa8AhqoIIO7t0ly3jdpU3PaHv1X080xnP9eRbUhEdQAyWYXWhpemZOOw89oumZuaFnwfv2NHsuD97sjLZX//WfvuNNlwV4NxbUxMHueUDBQnVsNCcamTXpEDPafv3XdH0Uj6AGCtZvV7thQq6osxjXYwFNOQhqoGChdrXb6FmMLGapHoIaKNi2gCWLYWe4HCZQTTxMBApW5q52HCZQTcyogYJttGQRAocJVBNBDZSgrIdyIcsuKA6lD2CEcJhANTGjBkZImWUXbBxBDYwYeqGrh9IHACSOoAaAxBHUAJA4ghoAEkdQA0Di6PpA7bDpEOqGoEatsOkQ6ojSB2qFTYdQRwQ1aoVNh1BHBDVqpdfmQmw6hCojqFErbDqEOuJhImqFTYdQRwQ1aodNh1A3lD4AIHHMqDGSWBSDKjF3D37Rqakpn5+fD35dIITuRTGSND5m+sErt+hbyysEN0phZifdfSrrPWbUGDlZi2JWVl1LyyuSWM2I9BDUGDl5Fr90VjPmDWpKKYiJoMbI6XUSd7e8qxn/ePaUHjzxkjpFRGbkCG1g14eZXW9mj5vZaTN73szuKWJgQCxZi2Ky5FnNOLvQuiSkO9hfBCHlmVGfl/RBd/+ymV0j6aSZPebuX4k8NiCK9YtiWkvLMpO6n6nnXc145PiZy0K6g/1FEMrAGbW7f8Pdv7z27/8r6bQk/n8OlbZvT/PizLo7pK+9elyH9+/OVbboF8bsL4JQhlrwYmY7JO2R9FTGewfMbN7M5hcXF8OMDogoq/tDkq6+ckvu2nKvMDaJ/UUQTO6gNrPXSXpY0u+7+7e733f3o+4+5e5Tk5OTIccIRBFiS9SserdJuvvm7TxIRDC5uj7MbFztkH7Q3Y/FHRJQjF7dH8OULNgECkUYGNRmZpI+Jum0u/9F/CEBxTi4d9dlKxQ3siUqm0Ahtjylj2lJ75V0m5k9vfbPnZHHBUS3b09Th/fvVnOiIZPUnGjkfogIFGngjNrdP6d22Q2IoqhVfb1+D8GM1LEyEaUq6tRwTidHlbEfNUpV1KnhnE6OKmNGjVJ0yhC99tzIapHbTImE08lRZQQ1Cpe1H3S37ha5zZYuQrTiAWWh9IHC9VoR2JHVIrfZ0gWnk6PKmFGjcP3KDc0eJY3Nli5YmIIqI6hRuF5liOZEQ58/dNtQf2bYVYQEM6qI0gcKt5EyBKULjDJm1CjcRsoQlC4wyjiFHAAS0O8UckofAJA4ghoAEkdQA0DieJhYkqJ2jANQfQR1CdjJDcAwKH2UgJ3cAAyDoC4BO7kBGAZBXYJey57ZyQ1AFoK6BCyHBjAMHiaWYLPLoekYAUYLQV2Sje7kRscIMHoofVQMHSPA6CGoK4aOEWD0UPoo0UZqzZz9B4weZtQl6dSaW0vLcr1Wa55daPX9c8N2jMwutDQ9M6edhx7R9MzcwOsDSA9BXZKN1pr37Wnq8P7dak40ZGofX3V4/+7MmfhGvwwApIXSR0l61ZRbS8uaXWgNPO0kT4dHvy8DOkSA6mBGXZJ+NeVQs14ePAL1QFCXJKvW3BGq3Y6l6kA9ENQl6dSaewkx62WpOlAPBHWJ9u1pqjlg1ruZro1hHjwCSBenkJese0m41J71dmbbvd4jbIF64RTyhPWb9bJcHIBEe14SerXb0bUBQMoxozazB8zsnJk9V8SA8Bq6NgBI+UofH5d0e+RxIANdGwCkHKUPd3/SzHbEHwq6bfaAAQD1EKxGbWYHJB2QpO3bt4e67Mjb6AEDAOojWFC7+1FJR6V2e16o6yKsrK1VJWbtQMro+hghWcd4Hfz0M5JLKxf84msc7QWkhT7qEZLVl72y6hdDuoNebSAtA2fUZvZJSbdI2mpmZyXd5+4fiz0whDdM/3W/z3IKOlCsPF0f7y5iIIiv1zFevT6bhVPQgeJR+hghWX3Z42Om8Svsktf69WqzrB0oHg8TR0ivvuys13rNjlnWDhSPoB4xvfqy85YtOAUdKB6lDwyFZe1A8ZhRYygsaweKR1BjaCxrB4pF6QMAEkdQA0DiCGoASBxBDQCJI6gBIHEENQAkjqAGgMQR1ACQOIIaABJHUANA4ghqAEgcQQ0AiSOoASBxBDUAJI6gBoDEEdQAkDiCGgASV/kTXmYXWhwLBaDWKh3Uswst3XvslJZXViVJraVl3XvslKT8p2pv9Pfy5QCgKJUufRw5fuZiSHcsr6zqyPEz0X5n58uhtbQs12tfDrMLrWi/E8Boq3RQv7y0PNTrIZTx5QBgtFU6qLdNNIZ6PYQyvhwAjLZKB/XBvbvUGB+75LXG+JgO7t0V7Xf2+hK4wozyB4AoKh3U+/Y0dXj/bjUnGjJJzYmGDu/fHfXBXtaXgyStulOrBhBFpbs+pHZYF9lx0fldH/zUM1p1v+S9Tq2aDhAAIVV6Rl2m7pDuoFYNILTKz6iL1mnP62V9DZt+awAh5ApqM7td0l9JGpN0v7vPRB3VJoQIx37XyGrP61j/ILOsxTgA6mdg6cPMxiT9raQ7JN0o6d1mdmPsgW1EiMUog67Rr7Sx/kEm/dYAQslTo75J0gvu/qK7f1/SQ5LuijusjQkRjoOu0as9rznRuGSmTL81gFDyBHVT0tfX/Xx27bVLmNkBM5s3s/nFxcUNDWZ2oaXpmTntPPSIpmfmhm51CxGOg66Rt3e7jMU4AOopT1BbxmuXtTy4+1F3n3L3qcnJyaEHEqJsESIcB10jb+92GYtxANRTnoeJZyVdv+7n6yS9HHog/UoOeR++Hdy765IHeNLw4ZjnGnl6t9fXqun6ALAZeYL6S5LeaGY7JbUkvUvSe0IPJETZIkQ4hgzYohfjAKingUHt7ufN7AOSjqvdnveAuz8feiDbJhpqZYTysDXdEOFIwAJISa4+and/VNKjMQcSomwRGgtWAKQgqZWJP7DliotBfe3V47rv195UWjCyYAVAKpLY66MTikvLKxdf+97KhRJHxIIVAOlIIqhTDEUWrABIRRJBnWIosmAFQCqSCOoUT01hwQqAVCQR1CmemlLG6TEAkCWJro9UT02hnxpACpKYUUvtULzAqSkAcJlkglriAR4AZEkqqHmABwCXS6JG3cGOcwBwuaSCWuIBHgB0S6r0AQC4HEENAIkjqAEgcQQ1ACSOoAaAxJn3WA24qYuaLUr6Ws6Pb5X0SvBBpG8U73sU71nivkfNRu/7x9x9MuuNKEE9DDObd/epUgdRglG871G8Z4n7LnscRYtx35Q+ACBxBDUAJC6FoD5a9gBKMor3PYr3LHHfoyb4fZdeowYA9JfCjBoA0AdBDQCJKyyozex2MztjZi+Y2aGM983M/nrt/WfN7K1FjS2WHPd899q9PmtmXzCzN5cxztAG3fe6z/2sma2a2TuLHF8see7bzG4xs6fN7Hkz+9eixxhajv/GX29m/2Rmz6zd8/vLGGdoZvaAmZ0zs+d6vB82z9w9+j+SxiT9p6Qfl3SlpGck3dj1mTslfVaSSbpZ0lNFjK3ke/55Sdeu/fsdVb/nvPe97nNzkh6V9M6yx13Q3/eEpK9I2r7284+UPe4C7vmPJH147d8nJf2PpCvLHnuAe/8lSW+V9FyP94PmWVEz6pskveDuL7r79yU9JOmurs/cJenvve2EpAkze0NB44th4D27+xfc/ZtrP56QdF3BY4whz9+1JP2epIclnStycBHlue/3SDrm7i9JkrtX/d7z3LNLusbMTNLr1A7q88UOMzx3f1Lte+klaJ4VFdRNSV9f9/PZtdeG/UyVDHs/v632N3DVDbxvM2tK+nVJHy1wXLHl+fv+SUnXmtkTZnbSzN5X2OjiyHPPfyPppyS9LOmUpHvc/UIxwytV0Dwr6oQXy3ituy8wz2eqJPf9mNmtagf1L0QdUTHy3PdHJH3I3VfbE61ayHPfWyS9TdIvS2pI+nczO+Hu/xF7cJHkuee9kp6WdJukn5D0mJn9m7t/O/bgShY0z4oK6rOSrl/383Vqf8MO+5kqyXU/ZvYzku6XdIe7/3dBY4spz31PSXpoLaS3SrrTzM67+2wxQ4wi73/jr7j7dyV918yelPRmSVUN6jz3/H5JM94u3L5gZv8l6QZJXyxmiKUJmmdFlT6+JOmNZrbTzK6U9C5Jn+n6zGckvW/taenNkr7l7t8oaHwxDLxnM9su6Zik91Z4VtVt4H27+0533+HuOyR9WtLvVjykpXz/jf+jpF80sy1mdrWkn5N0uuBxhpTnnl9S+/8gZGY/KmmXpBcLHWU5guZZITNqdz9vZh+QdFztJ8UPuPvzZvY7a+9/VO2n/3dKekHSq2p/E1dWznv+E0k/LOnv1maX573iu43lvO/ayXPf7n7azP5F0rOSLki6390z27uqIOff9Z9L+riZnVK7HPAhd6/81qdm9klJt0jaamZnJd0naVyKk2csIQeAxLEyEQASR1ADQOIIagBIHEENAIkjqAEgcQQ1ACSOoAaAxP0/m5oyYf9wzhUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "\n",
    "\n",
    "#画图\n",
    "def draw(pred=None):\n",
    "    plt.scatter(data[:, 1], data[:, -1])\n",
    "\n",
    "    if pred is not None:\n",
    "        plt.scatter(data[:, 1], pred)\n",
    "\n",
    "\n",
    "draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node col=0,value=1.00\n",
      "Leaf value=1.00\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#创建节点和叶子对象,用来构建树\n",
    "class Node():\n",
    "    def __init__(self, col, value):\n",
    "        self.col = col\n",
    "        self.value = value\n",
    "        self.lt_node = None\n",
    "        self.gt_node = None\n",
    "\n",
    "    def __call__(self, data):\n",
    "        if data[self.col] > self.value:\n",
    "            return self.gt_node(data)\n",
    "        return self.lt_node(data)\n",
    "\n",
    "    def __str__(self):\n",
    "        return 'Node col=%d,value=%.2f' % (self.col, self.value)\n",
    "\n",
    "\n",
    "class Leaf():\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "\n",
    "    def __call__(self, data):\n",
    "        return self.value\n",
    "\n",
    "    def __str__(self):\n",
    "        return 'Leaf value=%.2f' % self.value\n",
    "\n",
    "\n",
    "node = Node(0, 1)\n",
    "leaf = Leaf(1)\n",
    "\n",
    "print(node)\n",
    "print(leaf)\n",
    "\n",
    "node.lt_node = leaf\n",
    "\n",
    "node(np.array([0, 0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x7f185db8b780>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pickle\n",
    "\n",
    "#反序列化树\n",
    "s = b'\\x80\\x03c__main__\\nNode\\nq\\x00)\\x81q\\x01}q\\x02(X\\x03\\x00\\x00\\x00colq\\x03K\\x01X\\x05\\x00\\x00\\x00valueq\\x04cnumpy.core.multiarray\\nscalar\\nq\\x05cnumpy\\ndtype\\nq\\x06X\\x02\\x00\\x00\\x00f8q\\x07\\x89\\x88\\x87q\\x08Rq\\t(K\\x03X\\x01\\x00\\x00\\x00<q\\nNNNJ\\xff\\xff\\xff\\xffJ\\xff\\xff\\xff\\xffK\\x00tq\\x0bbC\\x08\\xcc]K\\xc8\\x07=\\xd9?q\\x0c\\x86q\\rRq\\x0eX\\x07\\x00\\x00\\x00lt_nodeq\\x0fh\\x00)\\x81q\\x10}q\\x11(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xf6\\xb7\\x04\\xe0\\x9fR\\xc9?q\\x12\\x86q\\x13Rq\\x14h\\x0fh\\x00)\\x81q\\x15}q\\x16(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xee\\xb45\"\\x18\\x07\\xc3?q\\x17\\x86q\\x18Rq\\x19h\\x0fc__main__\\nLeaf\\nq\\x1a)\\x81q\\x1b}q\\x1ch\\x04h\\x05h\\tC\\x08\\xb3\\xc3#\\xa265\\xa9\\xbfq\\x1d\\x86q\\x1eRq\\x1fsbX\\x07\\x00\\x00\\x00gt_nodeq h\\x1a)\\x81q!}q\"h\\x04h\\x05h\\tC\\x08\\xe7;9\\xc5\\xe7\\x8f\\xab?q#\\x86q$Rq%sbubh h\\x00)\\x81q&}q\\'(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xf8\\xdfJvl\\x04\\xd8?q(\\x86q)Rq*h\\x0fh\\x00)\\x81q+}q,(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08p\\x08Uj\\xf6@\\xd4?q-\\x86q.Rq/h\\x0fh\\x00)\\x81q0}q1(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xef8EGr\\xf9\\xcd?q2\\x86q3Rq4h\\x0fh\\x1a)\\x81q5}q6h\\x04h\\x05h\\tC\\x08sB\\xfbk\\x8c0\\xea?q7\\x86q8Rq9sbh h\\x1a)\\x81q:}q;h\\x04h\\x05h\\tC\\x08H\\xac\\x06\\xe3\\xe4\\x7f\\xf1?q<\\x86q=Rq>sbubh h\\x00)\\x81q?}q@(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xc6\\x18X\\xc7\\xf1C\\xd7?qA\\x86qBRqCh\\x0fh\\x1a)\\x81qD}qEh\\x04h\\x05h\\tC\\x08@J\\xec\\xda\\xde\\x0e\\xe8?qF\\x86qGRqHsbh h\\x1a)\\x81qI}qJh\\x04h\\x05h\\tC\\x08\\x8c\\x82\\xe0\\xf1\\xed]\\xef?qK\\x86qLRqMsbububh h\\x1a)\\x81qN}qOh\\x04h\\x05h\\tC\\x08\\xed\\t\\x12\\xdb\\xddC\\xf3?qP\\x86qQRqRsbububh h\\x00)\\x81qS}qT(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xb3\\x97m\\xa7\\xad\\x91\\xe2?qU\\x86qVRqWh\\x0fh\\x00)\\x81qX}qY(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08|\\xf1E{\\xbc\\x90\\xdf?qZ\\x86q[Rq\\\\h\\x0fh\\x1a)\\x81q]}q^h\\x04h\\x05h\\tC\\x08\\xa3\\x0bX\\xe0\\x99~\\xfe?q_\\x86q`Rqasbh h\\x00)\\x81qb}qc(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xdd\\\\\\xfcmO\\x10\\xe1?qd\\x86qeRqfh\\x0fh\\x00)\\x81qg}qh(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08<\\xa5\\x83\\xf5\\x7f\\x8e\\xe0?qi\\x86qjRqkh\\x0fh\\x1a)\\x81ql}qmh\\x04h\\x05h\\tC\\x08\\xfb\\xfa\\x9f\\xbf\\x8fH\\x01@qn\\x86qoRqpsbh h\\x1a)\\x81qq}qrh\\x04h\\x05h\\tC\\x08\\x8c\\xbc\\xac\\x89\\x05~\\x00@qs\\x86qtRqusbubh h\\x1a)\\x81qv}qwh\\x04h\\x05h\\tC\\x08y(\\xf7(I\\x84\\xfe?qx\\x86qyRqzsbububh h\\x00)\\x81q{}q|(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xe5\\x0e\\x9b\\xc8\\xcc\\x85\\xe9?q}\\x86q~Rq\\x7fh\\x0fh\\x00)\\x81q\\x80}q\\x81(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xc0Z\\xb5kB\\xda\\xe3?q\\x82\\x86q\\x83Rq\\x84h\\x0fh\\x1a)\\x81q\\x85}q\\x86h\\x04h\\x05h\\tC\\x08\\x7ff\\x10\\x1f\\xd8\\xe9\\x08@q\\x87\\x86q\\x88Rq\\x89sbh h\\x1a)\\x81q\\x8a}q\\x8bh\\x04h\\x05h\\tC\\x08\\xee\\xe1\\xc9\\x08\\x0c\\xef\\x07@q\\x8c\\x86q\\x8dRq\\x8esbubh h\\x00)\\x81q\\x8f}q\\x90(h\\x03K\\x01h\\x04h\\x05h\\tC\\x08\\xd1[<\\xbc\\xe7\\xc0\\xeb?q\\x91\\x86q\\x92Rq\\x93h\\x0fh\\x1a)\\x81q\\x94}q\\x95h\\x04h\\x05h\\tC\\x08\\xf4\\x84%\\x1eP\\x0e\\x0f@q\\x96\\x86q\\x97Rq\\x98sbh h\\x1a)\\x81q\\x99}q\\x9ah\\x04h\\x05h\\tC\\x08a\\r\\x8e\\xfc\\xa2\\x07\\x10@q\\x9b\\x86q\\x9cRq\\x9dsbubububub.'\n",
    "root = pickle.loads(s)\n",
    "root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=1,value=0.39\n",
      "-------- Node col=1,value=0.58\n",
      "------------ Node col=1,value=0.80\n",
      "---------------- Node col=1,value=0.87\n",
      "-------------------- Leaf value=4.01\n",
      "-------------------- Leaf value=3.88\n",
      "---------------- Node col=1,value=0.62\n",
      "-------------------- Leaf value=2.99\n",
      "-------------------- Leaf value=3.11\n",
      "------------ Node col=1,value=0.49\n",
      "---------------- Node col=1,value=0.53\n",
      "-------------------- Leaf value=1.91\n",
      "-------------------- Node col=1,value=0.52\n",
      "------------------------ Leaf value=2.06\n",
      "------------------------ Leaf value=2.16\n",
      "---------------- Leaf value=1.91\n",
      "-------- Node col=1,value=0.20\n",
      "------------ Node col=1,value=0.38\n",
      "---------------- Leaf value=1.20\n",
      "---------------- Node col=1,value=0.32\n",
      "-------------------- Node col=1,value=0.36\n",
      "------------------------ Leaf value=0.98\n",
      "------------------------ Leaf value=0.75\n",
      "-------------------- Node col=1,value=0.23\n",
      "------------------------ Leaf value=1.09\n",
      "------------------------ Leaf value=0.82\n",
      "------------ Node col=1,value=0.15\n",
      "---------------- Leaf value=0.05\n",
      "---------------- Leaf value=-0.05\n"
     ]
    }
   ],
   "source": [
    "#打印树的方法\n",
    "def print_tree(node, prefix=''):\n",
    "    prefix += '-' * 4\n",
    "    print(prefix, node)\n",
    "    if isinstance(node, Leaf):\n",
    "        return\n",
    "    print_tree(node.gt_node, prefix)\n",
    "    print_tree(node.lt_node, prefix)\n",
    "\n",
    "\n",
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((39, 3), (11, 3))"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#切分数据\n",
    "def split_data(data, col, value):\n",
    "    data_gt = data[data[:, col] > value]\n",
    "    data_lt = data[data[:, col] <= value]\n",
    "\n",
    "    return data_gt, data_lt\n",
    "\n",
    "\n",
    "data_gt, data_lt = split_data(data, 1, 0.2)\n",
    "data_gt.shape, data_lt.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAcCElEQVR4nO3df3Bd9Xnn8fcjWYLrOiMBVkIt2bHLULIbLGIQWWad3UnwZgkBguN21GySZpuh6+6ShoRtDfZORxBvuzbxTNPxbpiGcdO006REIazAENbL2qHZpCW1jLHMj3iXZkssuQwyjkwCl1qWnv3jSLZ0dc6950rnnnOu7uc145HuOd9zzvdgz3O/PN9f5u6IiEh+NWVdARERKU+BWkQk5xSoRURyToFaRCTnFKhFRHJuSS1uunz5cl+9enUtbi0isigdOnTopLt3hJ2rSaBevXo1g4ODtbi1iMiiZGYvR51T6kNEJOcUqEVEck6BWkQk5xSoRURyToFaRCTnajLqQ0SklgYOj7Br3zFOjBVZ0V5gyw1XsHFdZ9bVqhkFahGpKwOHR9j28FGK4xMAjIwV2fbwUYBFG6yV+hCRurJr37FzQXpacXyCXfuOZVSj2lOgFpG6cmKsWNXxxUCBWkTqyor2QlXHFwMFahGpK1tuuIJCS/OsY4WWZrbccEVGNQry5ut3HmDN1sdZv/MAA4dHEr2/OhNFJBfijuSYPpaXUR9pdG4qUItI5qoNdhvXdeZmhEe5zk0FahFZNNIIdtOSHoOdRuemctQikrm0RnJMt9xHxoo451vuC8kpp9G5qUAtIplLayRHLcZgp9G5qUAtIpn7wLs6sJJjtRjJUYuW+8Z1nezYtJbO9gIGdLYX2LFpbaIpG+WoRSRTA4dH+PahEXzGMQN+5ZrkOwxXtBcYCQnKC22517pzUy1qEclUWDrCge/+aDTxZ+VxDHYcalGLSKbS6EicOdKjrdDChS1NjL05nvkY7LhiB2ozawYGgRF3v7l2VRKRRjKvdMRQP+zfDqeHoa0LNvRBd29o0YHDI3z/v9/PN3mQFRec5KcTyzAzLrrw59gFXdDcB4RfG/rcJ+6G4qngc+FiePdH4ciDMP5GcMya4JpPw81/GO+eMVST+vgc8GJiTxYRYR7piKF+2HsHnD4OePBz7x3B8RDPPv4A2+0BuppO0mRwSdPPudh+hsW4ds5zB24/H6Qh+H3wT84HaQCfDI499h8r3zOmWIHazLqAm4A9iT1ZRIR5jJrYvx3GS1rg48XgeIjfPPMXLLUz0RUoc+2c506OVy437dDX4petIG7q44+Au4C3RRUws83AZoBVq1YtvGYi0jCqGjVxeriq4yuaXpv/PastM5NPVC4TU8UWtZndDLzq7ofK1sn9AXfvcfeejo6OxCooIjJLW1dVx98qXDr/e1ZbZiZrrlwmpjipj/XAR8zs74EHgevN7C8Sq4GIyFA/3LcG7m0L/ty3JjpvvKEPWko6GlsKwfEQS2/cztnmC6OfXebaOc9taplz2EOKAnDNb1S+Z0wVA7W7b3P3LndfDXwMOODun0ysBiLS2KI66R75THiw7u6FW3ZD20rAgp+37I4c9UF3L0tu/a/nyxcuDv7EubbkPgff8wec8mW4gzuc8mV8Y/KDjDfN+OKwJui5LdFRH+Ye+X0wt7DZ+4HfrTQ8r6enxwcHBxdYNRFpCF+6cmoER4i2lXDnc+nWp4z1Ow+EDiXsbC/wg63XL+jeZnbI3XvCzlU14cXdnwKeWlBtRERmKtdJV20HXo1FTcIZGSuyfueBmm1koCnkIpKtcp101Xbg1VjUJByDRJdOLaVALSLZiuiko7k1XidfisIm5xhzOxQXunRqKQVqEclWdy9svH+qg29K4WK49cvxOvlSFDY5J6qXL8m1SrQok4hkr7s3d0E5TOk2Xh94Vwdff/onocE6yU0PFKhFRGII24A3KkgbaIcXEZG0Ra2bHcYJ3z19vhSoRURiqCbn3JnwXo8K1CIiMZQbmjdTLXaMUaAWEYkhat3sT1y3qqYb24I6E0VEYpkOvjNHfaS1jZcCtYhITLXebTyKUh8iIjmnQC0iknMK1CIiOadALSKScwrUIiI5p0AtIpJzCtQiIjmnQC0iknMK1CIiOadALSKSc5pCLrJIlO4+ktY6FFJ7CtQii0DY7iPbHj4KJLuAvWRDgVokBbVu7YbtPjK9E7YCdf1ToBapsTRau1G7jyS5E7ZkR52JIjVWrrWblKjdR5LcCVuyo0AtUmNptHajdh9JeksoyYYCtUiNpdHa3biukx2b1tZ8SyjJhnLUIjW25YYrZuWooTat3ax2H5HaU6AWWaihfnjibiieCj4XLoYb74PuXiAIoJ3HH2PlM7t4u4/yqnVw/OotXLvuQxlWWuqJArXIQgz1w8DtMDl+/ljxFDzymeD37l4Y6ufao/cARTC4lFEuPXoPrL7oXDAXKUc5apGF2L99dpCeNnEmODddZryk43C8eP68SAVqUYssxOnhyueiypS7NiGaVr44qEUtshBtXZXPRZUpd20CpifajIwVcc5PtBk4PFLT50ryKraozexC4HvABVPlH3L3e2pdMZG6sKFvbo4aoLk1ODddZu8ds9Mfza1w5g24tz0I2Bv6qs9Xl3ZitvwCLLkAij+Fti6efeNX+ODEGe5q7WeFneSEL+eLZ3t59vG/YeNT3w5a9FHPHuoPUjOlZUqPX/6v4f/+z/L3kgUzdy9fwMyAX3D3n5tZC/B94HPu/nTUNT09PT44OJhsTUXyqsKoj3NlpgNc4SL4x5/NDu4tBbhld/wgN9QfdFhOnIkscsaX4DgX2ETZY3OePdQ/94ulpQBXfRyOfGNuvn2mat9DzjGzQ+7eE3quUqAuudFSgkD9H9z9h1HlFKhFyvjSlXD6+NzjbSvhzucWdo/5mvnsqHtbM/jE3OPl7iWxlQvUsXLUZtZsZs8CrwJPhgVpM9tsZoNmNjg6OrqwGossZkl0LibdETnzflH3jhOky10v8xYrULv7hLu/B+gC3mtmV4aUecDde9y9p6OjI+l6iiweSXQuJt0ROfN+Ufe25vDj5e4liahq1Ie7jwFPAZpSJTJfG/qCXO5MLYXznY9x79HcWr5Mcys0tVQ+VvrsqPpd8xtzj5eq9j0kloqB2sw6zKx96vcC8K+AH9W6YiKLVndv0OHWthKw4Ge1HXDdvRy86vcZ4224gwPjTYWgI3P6nrd+GTbeP/s5YcdKn93dy8G1X+AVOph04xU6OLj2C3DzH86td89tC3sPiSXOqI9u4M+AZoLA3u/uZadUqTNRpLZKNyOAYKGnJFbMK3dvYNYEmg+8q4Pv/mhUE2oSkNioj7gUqEVqa/3OA4yErGfd2V7gB1uvr8m9L1rawlvjk3M2QZgpqS+LRrTgUR8iki9Rmw6EBdik7v3TN8fLBmlIfucaCShQi9ShqE0HDBY8RXyhGxpon8bkKVCL1KEtN1yBhRx3WHCLNmpbr/ZCS8QVs2mfxuQpUItkYODwCOt3HmDN1sdZv/NA1a3gjes6iepdWmiLNmpbr3s/8u45AbyU9mmsDS1zKpKy0lEV06vaAVV1wnW2F0Jz0km0aMtt66VRH+lToBZJ2a59x+Z0yk13wlUT5NLai3Em7cuYDQVqkZRFpSaqTVlMB8xqNwbQZgL1R4FaJGUrEkxZVNvCTSrtIulSZ6JIyqJGVaTRCVcu7SL5pRa1SMrmm7JIQlJpF0mXArVIBrLqlEsy7SLpUepDpIFkmXaR+VOLWqSBZJl2kflToBZpMBoLXX+U+hARyTkFahGRnFOgFhHJOQVqEZGcU6AWEck5jfqQRUeLDslio0Ati4oWHZLFSKkPWVS06JAsRgrUsqho0SFZjBSoZVGJWlxIiw5JPVOglkVFiw7JYqTORFlUtOiQLEYK1LLoRC46NNQP+7fD6WFo64INfdDdm34FRaqkQC2NYagf9t4B41OdiqePB59BwVpyTzlqaQz7t58P0tPGiww/tI31Ow8wcHgkm3qJxKAWtTSG08Ohh1fYa4yMFdny0BHuffR5ThfHldeW3FGLWhpDW1fo4RN+CQDjE85YcRzn/GxGtbIlL9SilsawoW92jhqYdOi0k7x0wSdpYpJJmmhmkhFfzhfP9rJrX2vsVrXWF5FaUqCWxjDdYbh/O5Onj4NDkwWHljAJQNPUzy47yc6WPWx7HeD6irf+vYGjfP3pn+BTn7W+iCStYurDzFaa2XfN7EUze97MPpdGxUQS190Ldz7HW4VfPBekoyy1M2xr/VbFWw4cHpkVpKdpfRFJUpwW9Vngd9z9GTN7G3DIzJ509xdqXDeRmlhafCVWuXdwsmKZXfuOzQnS07S+iCSlYova3f/B3Z+Z+v1nwIuA/n9O6ldEx2Ipi1GuXDDW+iKSlKpGfZjZamAd8MOQc5vNbNDMBkdHR5OpnUgtbOiDlgpBtKUQlKsgKhgbaH0RSUzsQG1my4BvA59399dLz7v7A+7e4+49HR0dSdZRFqOhfvjSlXBvO9y3Jvhzb3twbKi/8jULKdfdC7fsZnhyOe5w1puYnPrpDsOTy+GW3bFmLIYtAmXAJ65bpY5ESUysUR9m1kIQpL/u7g/Xtkqy6JVO5y6eOn8uamp33Cngcct19/Jr31nOSEjqorO9wA+6K4/2AC0CJekw96iukKkCZgb8GXDK3T8f56Y9PT0+ODiYQPVkUfrSlUEALadtJdz5XOVr5luOudt2QbAk6o5NaxVoJXVmdsjde8LOxUl9rAd+HbjezJ6d+vPhRGsojSViOnfZMlHXzLccQWt4x6a1dLYXMIKWtIK05FHF1Ie7f58g7SaSjLauGC3qrrmfQ1vK8ctFzR5UYJa801ofkr4Koy6K3srByz5b+ZqwkRkR5Q5e9lm2PXyUkbGi1vOQuqNALembGnVB20omMV6bXMYpX8akG8OTy7l7/Df5/AuXR14DFvwMG5kRUe7zL1yu3cmlbmmtD8nEwMR6dv3jbkbeCp8wYiGjMaavOfFWkRUXFtgycQUbwy7u7p0TwE984/HQ52j2oNQDBWpJXdhoi1KlE0lKr6l24aMV7YXQoXiaPSj1QKkPSd2ufcfKBumwXcPDrqkmdaHdyaWeqUUtqSuXbuiMmDASdU3c1IUmpkg9U6CW1EWlITrbC/xga/iMwCRSFxqKJ/VKqQ9J3XzSEEpdSCNTi1pSN580hFIX0sgqrvUxH1rrQ0SkOgtd60NERDKkQC0iknMK1CIiOafOxIxEreQmIlJKgToDC50OLSKNRamPDCx0OrSINBYF6gwsdDq0iDQWBeoMRE171kpuIhJGgToDmg4tItVQZ2IGFjodWiNGRBqLAnVG5ruSm0aMiDQepT7qjEaMiDQeBeo6oxEjIo1HqY8MzSfXrL3/RBqPWtQZmc41j4wVcc7nmgcOj5S9rtoRIwOHR1i/8wBrtj7O+p0HKt5fRPJHgToj8801b1zXyY5Na+lsL2AE21ft2LQ2tCU+3y8DEckXpT4yEpVTHhkrMnB4pOJuJ3FGeJT7MtAIEZH6oRZ1RsrllJNq9arjUWRxUKDOSFiueVpSw+00VV1kcVCgzsh0rjlKEq1eTVUXWRyUo87QxnWd7Np3rOxwu4OPfoWVz+zi7T7Kq9bB8au3cO3qi2D/djg9DG1dsKEPuntD7995/LFZ17/xzg1c9tTvwiPlrxWR/NAu5BkrnRIOQat3x6a1dB5/jCsP/R4FO3Pu3BlvprmpiWYfP3+TlgLcsntuwB3qh713wHiZ1nnUtSKSKu1CnmPlhtutfGbXrCAN0GoTs4M0BIF4//a5N9+/vXyQLnetiOSGUh85EDXc7u0+ChbzJqeH4x2Le62I5EbFFrWZfdXMXjWz59KokJz3qnXEL9zWFe9Y3GtFJDfipD6+BnyoxvWQEMev3kLRW2cdO+PNTFjL7IIthaBTsNSGvuBcOVHXikhuVAzU7v494FQKdZES137kt3jumt/nFTqYdOMVOjhyzQ6aP3o/tK0ELPgZ1RnY3Rucm1m257Z414pIbsQa9WFmq4HH3P3KMmU2A5sBVq1adc3LL7+cUBVFRBa/cqM+EutMdPcHgAcgGJ6X1H0lWWFLq8L8twUTkdrTqI8GEraN15aHjoDD+KSfO6atvUTyReOoG0jYanrjE34uSE/T1l4i+VKxRW1mfwm8H1huZsPAPe7+J7Wu2KI31A9P3A3F6X5aAzzo4KvRtO5q1g8pV1a7oIukq2Kgdvd/k0ZFGspQPzzyGZiYOetwqlV7+ngw7RsSD9ZR23hFlQ2jXdBF0qfURxb2by8J0iVqNK07bDW9lmajpWn29MdyK+xpF3SR9KkzMQtxpmzXYFr3dIu3NG1RusLe8au3cO268DlOJ8aKfKTp+9y1pJ8VdpITvpwvnu1l79j7Eq+viAQUqLPQ1hWkOCqVqYE564oM9cPRe4AiGFzKKJcevQdWXxSaevm3y/6Wu8b3sHRqsaguO8nOlj1c3NIK3FSTOos0OqU+srChD5pbo8+nOa07bIW9MqmXu1q+eS5IT1tqZ7ir5Zu1qqFIw1OgzkJ3L9z6ZShcPOPgVJ447WndUSmWiONLi69UdVxEFk6pj6x09+ZjjY2oNExU6qXa8iKyYGpRN7qwFfbKpV6qLS8iC6ZA3ejCVtgrl3qptryILJj2TBQRyQHtmSgiUscUqEVEck6BWkQk5xSoRURyToFaRCTnFKhFRHJOgVpEJOcUqEVEck6BWkQk5xSoRURyToFaRCTnFKhFRHJOgVpEJOcUqEVEcq7ud3gZODwyZ1ftWZu3iojUuboO1AOHR9j28FGK4xMAjIwV2fbwUYCaBmt9OYhImuo69bFr37FzQXpacXyCXfuO1eyZ018OI2NFnPNfDgOHR2r2TBFpbHUdqE+MFas6noQsvhxEpLHVdaBe0V6o6ngSsvhyEJHGVteBessNV1BoaZ51rNDSzJYbrqjZM6O+BJrMlP4QkZqo60C9cV0nOzatpbO9gAGd7QV2bFpb0469sC8HgAl35apFpCbqetQHBME6zREX08/6nf4jTJTs4D6dq9YIEBFJUt0H6iysfXY7x1r7aWby3LERX84Xz/ayd+x95wsO9cP+7XB6GNq6YEMfdPdmUGMRqWcK1FX6uz/9LX7p7x/EbPbxLjvJzpY9XNzSCtwEQ/2cfeSzLJl4Kyhw+njwGRSsRaQqsXLUZvYhMztmZi+Z2dZaV2ohBg6PsH7nAdZsfZz1Ow/MK2dc7h7vfLl/TpCettTOcFfLNwF484m+80F6ypKJt3jzib6q6yMija1ii9rMmoEvAx8EhoGDZvaou79Q68pVK4mZipXu0eyTEBGoAZYWXwHgwqmfpaKOi4hEiZP6eC/wkrv/GMDMHgRuBZIN1EP98MTdUDx1/ljhYrjxvvKpghl54OtYzla/ig2tz7LCTnJiKm+8a19r7EC9a98xPjjxV9zV2k+nnWSCJpqY5NVHOqD5vzBhTSyZkZueo60LgBOTl9DVdHLO6ROTl9AVqyYiIoE4qY9O4PiMz8NTx2Yxs81mNmhmg6Ojo9XVYqgfBm6fHaQh+Dxwe3A+6rq9d8Dp44BzKaN8qvl/0dV0kiaDrqYgb9zz+pOxq9Lz+pPsbNlDV9NJzGCJTdJkcCmjsPcOXrvkvZQM9jivpRB0GAJ7Wj/Jm9466/Sb3sqe1k/GrouICMQL1GH/oz8nVLn7A+7e4+49HR0d1dVi/3aYHA8/NzkenI+6bnz2jMDS/PFSO8O21m/Frsq21m+x1M6Enxwv8o6zI/x49cc4SxPuwX8IB2hbCbfsPtf6f89Nm+nzzQxPLmfSjeHJ5fT5Zt5z0+bYdRERgXipj2Fg5YzPXcCJRGtxenh+5ytdN+UdzE1BzLvs6WEuu/MrwFfKFgtSLbfza/s2aJU9EVmQOIH6IHC5ma0BRoCPAR9PtBZtXVPpizLn53PdFIu6PqrsfOoSIu3JOCKyOFVMfbj7WeC3gX3Ai0C/uz+faC029HGGudOygeD4hoghbRv6grxwOTPyxnHrEnnPau8lIpKAWOOo3f077v7L7n6Zu/9B4rXo7uXI1Ts45cuCvO/Un1O+jCNX74ge9dHdG+SF21YCFvzsuW325xl547h1mb6nA2dpYtLhFTo4uPYLmqwiIqnLzczEkZU38+8Or2GsGHQqXrS0hXtueXfl1EF3b/LBs7uXgYn1s8ZTAxQONrNj5YjSGSKSqlysnjc9yWQ6SAO8NV5mrHIKtEGAiORFLgJ1HoOiNggQkbzIRaDOY1DMYvcYEZEwuQjUedw1JYvdY0REwuQiUOdx15Qsdo8REQmTi1Efed01RRNWRCQPctGihiAoTkasdqQOPBFpZLkJ1KAOPBGRMLkK1OrAExGZKxc56mnT+eBd+45pxTkRkSm5CtSgDjwRkVK5Sn2IiMhcCtQiIjmnQC0iknMK1CIiOadALSKSc+YRswEXdFOzUeDlmMWXQxW7zy4ejfjejfjOoPduNPN973e6e0fYiZoE6mqY2aC792RaiQw04ns34juD3jvreqStFu+t1IeISM4pUIuI5FweAvUDWVcgI4343o34zqD3bjSJv3fmOWoRESkvDy1qEREpQ4FaRCTnUgvUZvYhMztmZi+Z2daQ82Zmu6fOD5nZ1WnVrVZivPMnpt51yMz+2syuyqKeSav03jPKXWtmE2b2q2nWr1bivLeZvd/MnjWz583sr9KuY9Ji/BtvM7O9ZnZk6p0/nUU9k2ZmXzWzV83suYjzycYzd6/5H6AZ+Dvgl4BW4AjwT0vKfBh4AjDgOuCHadQt43f+58BFU7/fWO/vHPe9Z5Q7AHwH+NWs653S33c78AKwaurz27Oudwrv/J+A+6Z+7wBOAa1Z1z2Bd/+XwNXAcxHnE41nabWo3wu85O4/dvczwIPArSVlbgX+3ANPA+1m9osp1a8WKr6zu/+1u/906uPTQFfKdayFOH/XAJ8Fvg28mmblaijOe38ceNjdfwLg7vX+7nHe2YG3mZkBywgC9dl0q5k8d/8ewbtESTSepRWoO4HjMz4PTx2rtkw9qfZ9biP4Bq53Fd/bzDqBjwJ/nGK9ai3O3/cvAxeZ2VNmdsjMPpVa7Wojzjv/N+CfACeAo8Dn3H0yneplKtF4ltYOLxZyrHRcYJwy9ST2+5jZBwgC9ftqWqN0xHnvPwLudveJoKG1KMR57yXANcAGoAD8jZk97e7/p9aVq5E473wD8CxwPXAZ8KSZ/W93f73WlctYovEsrUA9DKyc8bmL4Bu22jL1JNb7mFk3sAe40d1fS6lutRTnvXuAB6eC9HLgw2Z21t0H0qliTcT9N37S3d8A3jCz7wFXAfUaqOO886eBnR4kbl8ys/8HvAv423SqmJlE41laqY+DwOVmtsbMWoGPAY+WlHkU+NRUb+l1wGl3/4eU6lcLFd/ZzFYBDwO/XsetqlIV39vd17j7andfDTwE3F7nQRri/Rt/BPgXZrbEzJYC/wx4MeV6JinOO/+E4P8gMLN3AFcAP061ltlINJ6l0qJ297Nm9tvAPoKe4q+6+/Nm9u+nzv8xQe//h4GXgDcJvonrVsx37gMuAe6fal2e9TpfbSzmey86cd7b3V80s/8BDAGTwB53Dx3eVQ9i/l3/Z+BrZnaUIB1wt7vX/dKnZvaXwPuB5WY2DNwDtEBt4pmmkIuI5JxmJoqI5JwCtYhIzilQi4jknAK1iEjOKVCLiOScArWISM4pUIuI5Nz/B2g2YjGWtRNrAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#预测\n",
    "pred = np.empty(N)\n",
    "for i in range(N):\n",
    "    pred[i] = root(data[i])\n",
    "\n",
    "draw(pred)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.8179390484424856"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#计算树节点的loss,也就是误差平方和\n",
    "def get_loss(node, data):\n",
    "    _sum = 0\n",
    "    for di in data:\n",
    "        _sum += np.power(node(di) - di[-1], 2)\n",
    "    return _sum\n",
    "\n",
    "\n",
    "get_loss(root, data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#剪切节点\n",
    "def cut_node(node, data):\n",
    "    print_tree(node)\n",
    "    print('===========================================================')\n",
    "\n",
    "    #叶子节点不存在剪枝\n",
    "    if isinstance(node, Leaf):\n",
    "        return node\n",
    "\n",
    "    #只有两边都是叶子的节点才能剪枝\n",
    "    if isinstance(node.gt_node, Node) or isinstance(node.lt_node, Node):\n",
    "        return node\n",
    "\n",
    "    #求两边值的均值,定义为新的leaf\n",
    "    mean_value = (node.gt_node.value + node.lt_node.value) / 2\n",
    "    cut_leaf = Leaf(mean_value)\n",
    "\n",
    "    #计算loss\n",
    "    cut_loss = get_loss(cut_leaf, data)\n",
    "\n",
    "    #计算剪枝前的loss\n",
    "    data_gt, data_lt = split_data(data, node.col, node.value)\n",
    "    gt_loss = get_loss(node.gt_node, data_gt)\n",
    "    lt_loss = get_loss(node.lt_node, data_lt)\n",
    "\n",
    "    print('cut=', cut_loss < gt_loss + lt_loss)\n",
    "\n",
    "    #如果剪枝后loss下降了,则剪枝,否则保持原样\n",
    "    if cut_loss < gt_loss + lt_loss:\n",
    "        return cut_leaf\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=1,value=0.87\n",
      "-------- Leaf value=4.01\n",
      "-------- Leaf value=3.88\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.62\n",
      "-------- Leaf value=2.99\n",
      "-------- Leaf value=3.11\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.80\n",
      "-------- Leaf value=3.94\n",
      "-------- Leaf value=3.05\n",
      "===========================================================\n",
      "cut= False\n",
      "---- Node col=1,value=0.52\n",
      "-------- Leaf value=2.06\n",
      "-------- Leaf value=2.16\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.53\n",
      "-------- Leaf value=1.91\n",
      "-------- Leaf value=2.11\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.49\n",
      "-------- Leaf value=2.01\n",
      "-------- Leaf value=1.91\n",
      "===========================================================\n",
      "cut= False\n",
      "---- Node col=1,value=0.58\n",
      "-------- Node col=1,value=0.80\n",
      "------------ Leaf value=3.94\n",
      "------------ Leaf value=3.05\n",
      "-------- Node col=1,value=0.49\n",
      "------------ Leaf value=2.01\n",
      "------------ Leaf value=1.91\n",
      "===========================================================\n",
      "---- Node col=1,value=0.36\n",
      "-------- Leaf value=0.98\n",
      "-------- Leaf value=0.75\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.23\n",
      "-------- Leaf value=1.09\n",
      "-------- Leaf value=0.82\n",
      "===========================================================\n",
      "cut= True\n",
      "---- Node col=1,value=0.32\n",
      "-------- Leaf value=0.87\n",
      "-------- Leaf value=0.96\n",
      "===========================================================\n",
      "cut= False\n",
      "---- Node col=1,value=0.38\n",
      "-------- Leaf value=1.20\n",
      "-------- Node col=1,value=0.32\n",
      "------------ Leaf value=0.87\n",
      "------------ Leaf value=0.96\n",
      "===========================================================\n",
      "---- Node col=1,value=0.15\n",
      "-------- Leaf value=0.05\n",
      "-------- Leaf value=-0.05\n",
      "===========================================================\n",
      "cut= False\n",
      "---- Node col=1,value=0.20\n",
      "-------- Node col=1,value=0.38\n",
      "------------ Leaf value=1.20\n",
      "------------ Node col=1,value=0.32\n",
      "---------------- Leaf value=0.87\n",
      "---------------- Leaf value=0.96\n",
      "-------- Node col=1,value=0.15\n",
      "------------ Leaf value=0.05\n",
      "------------ Leaf value=-0.05\n",
      "===========================================================\n"
     ]
    }
   ],
   "source": [
    "#后剪枝算法\n",
    "def cur_tree(node, data):\n",
    "\n",
    "    #如果已经是个叶子节点了,就不存在剪枝\n",
    "    if isinstance(node, Leaf):\n",
    "        return\n",
    "\n",
    "    #切分数据集\n",
    "    data_gt, data_lt = split_data(data, node.col, node.value)\n",
    "\n",
    "    #如果是个节点,则先向下遍历寻找子节点,子节点都切完之后再尝试切自己\n",
    "    if isinstance(node.gt_node, Node):\n",
    "        cur_tree(node.gt_node, data_gt)\n",
    "        node.gt_node = cut_node(node.gt_node, data_gt)\n",
    "\n",
    "    if isinstance(node.lt_node, Node):\n",
    "        cur_tree(node.lt_node, data_lt)\n",
    "        node.lt_node = cut_node(node.lt_node, data_lt)\n",
    "\n",
    "\n",
    "cur_tree(root, data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---- Node col=1,value=0.39\n",
      "-------- Node col=1,value=0.58\n",
      "------------ Node col=1,value=0.80\n",
      "---------------- Leaf value=3.94\n",
      "---------------- Leaf value=3.05\n",
      "------------ Node col=1,value=0.49\n",
      "---------------- Leaf value=2.01\n",
      "---------------- Leaf value=1.91\n",
      "-------- Node col=1,value=0.20\n",
      "------------ Node col=1,value=0.38\n",
      "---------------- Leaf value=1.20\n",
      "---------------- Node col=1,value=0.32\n",
      "-------------------- Leaf value=0.87\n",
      "-------------------- Leaf value=0.96\n",
      "------------ Node col=1,value=0.15\n",
      "---------------- Leaf value=0.05\n",
      "---------------- Leaf value=-0.05\n"
     ]
    }
   ],
   "source": [
    "print_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAasklEQVR4nO3df3Dcd33n8edb61WyxiDFsUtiya7TXGoOsEMSwWXO3A1ETZ1A3Li5Vs0BZcrQ+nqhSWEYxzZ3o1LfXO3gmYa6B9N6fBxlCk3Vw1UIIWdydinXtKGRcSyHBB+Ba7BkmNhxrBS8iWTt5/747lrS6vvd/a70/bW7r8dMRt7v9/P97ucbZ1765P39fL8fc84hIiLZ1ZF2B0REpDYFtYhIximoRUQyTkEtIpJxCmoRkYxbEsdJV6xY4dauXRvHqUVEWtLRo0fPOudW+u2LJajXrl3LyMhIHKcWEWlJZvZC0D6VPkREMk5BLSKScQpqEZGMU1CLiGScglpEJONimfUhIhKn4WPj7D10ktPni6zqLrBt0zq23NCTdrdio6AWkaYyfGycnQdPUJyaBmD8fJGdB08AtGxYq/QhIk1l76GTl0K6ojg1zd5DJ1PqUfwU1CLSVE6fLza0vRUoqEWkqazqLjS0vRUoqEWkqWzbtI5CPjdnWyGfY9umdSn1yKubb9xzhGt2PMrGPUcYPjYe6fl1M1FEMiHsTI7KtqzM+kji5qaCWkRS12jYbbmhJzMzPGrd3FRQi0jLSCLsKqKeg53EzU3VqEUkdUnN5KiM3MfPF3HMjNwXU1NO4uamglpEUpfUTI445mAncXNTQS0iqXv3m1ZiVdvimMkRx8h9yw097L5rPT3dBQzo6S6w+671kZZsVKMWkVQNHxvny0fHcbO2GfDvbor+huGq7gLjPqG82JF73Dc3NaIWkVT5lSMc8DffPRP5d2VxDnYYGlGLSKqSuJE4e6ZHVyHP5fkOzl+YSn0Odlihg9rMcsAIMO6cuyO+LolIO4mrHFFRPUf7fHGKQj7Hg7/2tswHdEUjpY/fBZ6LqyMi0p7iLke0wtv2QgW1mfUC7wUOxNsdEWk3cc+aaIW37YUtfXwauB94fVADM9sKbAVYs2bN4nsmIm1jS+4Jtth2uPwcvAp8fTnkHoANA/4HjA7B4V0wMQZdvdA/GNh2VXeBm155nPuXDLHKzvKyW4YZdNtP4cHax/p+72PboXjO+1xYDm/5ZTj+EEz91NtmHXDTh+COP2zsX0INdYPazO4AXnTOHTWzdwW1c87tB/YD9PX1uaB2IiJzjA7B8D1QmprZVjwHD3/E+3N1iI4OwSP3wVR5RDxxyvvs1xb49Ju/x1uPHqBgkwBcaT+Z2Vnn2FD9HPnvc9u50sy2iMI6TOljI/BLZvZPwEPALWb255F8u4jI4V1zw69ietLb59d+qqpsMVX0bwu8/ft/fCmkfdU4NlQ/gxz9fPi2ddQNaufcTudcr3NuLXA3cMQ594HIeiAi7W1irLF9Qe0b3R5Hm9ncdP02IemBFxFJV1dvY/uC2je6PY42s1mufpuQGgpq59w3NIdaRCLVPwgd+fnbc53ePr/2+ao51vmCf9ug9mGPrTrPa25++DqfO3IO4KbfqH/OkDSiFpF0bRiALZ/1ZlBUFJbDnZ/xv8G3YQA274Ou1YB5PzfvC74ZWN2+sLz8XSGOrTrP7vy9vFRahnNeQJ9zy/jC9C/wz6XLLm2bdsaXSrcy3PPxBfzL8GfO79fBIvX19bmRkZHIzysikqbqpxzBe4GUX4r2dBd4Ysctoc9tZkedc31++zSiFhEJye/hnKChrlZ4ERFJQfUyXn7v0a6IctEDvT1PRCQEvwV4v/jkD31H1AZa4UVEJGlB78324/BfPX2hFNQiIiE0UnPuiXitRwW1iEgIQTXnJNZ6VFCLiIQQ9N7s99+8JtaFbUE3E0VEQqmE7+xZH0kt46WgFhEJKe7VxoOo9CEiknEKahGRjFNQi4hknIJaRCTjFNQiIhmnoBYRyTgFtYhIximoRUQyTkEtIpJxCmoRkYzTI+QiLaJ69ZGk3kMh8VNQi7QAv9VHdh48AUT7AntJh4JaJAFxj3b9Vh8pTk2z99BJBXULUFCLxCyJ0W7Q6iNRroQt6dHNRJGY1RrtRiVo9ZEoV8KW9CioRWKWxGg3aPWRqJeEknQoqEVilsRod8sNPey+a33sS0JJOlSjFonZtk3r5tSoIZ7Rblqrj0j8FNQiMUtzrT1pDQpqkQRotCuLoaAWWazRIXhsOxTPeZ8Ly+H2B2DDwNw2h3fBxBh09cJ1vwjf+/rM5/7Bue0X8r3518GSy6D48sw5Ye73Bm2r/u7q/lbaxHEdUpc55yI/aV9fnxsZGYn8vCKZMzoEw/dAaWru9lwn3PmZmXB75D6YqjHLI1+AzfvCh9zoEDz8EZieDG6T62S6VCLnLl7aNG15csbc/lZ/t19/8wW4/n1w/EvRXodcYmZHnXN9fvs060NkMQ7vmh/S4AXo4V0zbWqFG3j7K+3Dfm+tkC73YXZIA+Tc1Pz+Vn+3X3+ninD089Ffh4RSN6jN7HIz+0czO25m3zGz30+iYyJNYWKs/r5abcKeazFtGz1f0LndtP/2WueSSIQZUb8G3OKcux54G3Cbmd0cb7dEmkRXb/19tdqEPddi2jZ6vqBzW85/e61zSSTqBrXz/KT8MV/+J/rCtkgz6h+Ejvz87bnOmRt3/YNe7baWfGGmfdjvzXXWbDLJEl5zc8N10i1hkqrArf5uv/7mC3DTb0R/HRJKqBq1meXM7GngReBx59y3fNpsNbMRMxs5c+ZM1P0UyaYNA7Dls95Mj4rC8pkbiZU2m/dB12rAvJ99H577udEbcBsGvO+Y/b3515U/e+c8fuMf8J/cf2SstIKSM8ZKK/iE+22O37i79nf79XfzPrjjD6O/DgmloVkfZtYN/DVwr3PumaB2mvUhkg1aTKB51Jr10dA8aufceTP7BnAbEBjUIpINetCmNdQNajNbCUyVQ7oA/ALwQOw9E5Ga4hwtaySeLWFG1FcDf2ZmObya9pBz7qvxdktEaolzMYJa54a57yx595tW8jffPaNAj5meTBRpQhv3HGHc533WPd0FnthxSyznvmJpnlenSvMWQZitkM/p9aoLpCcTRVpM0KIDfgEb1blfvjBVM6Qh+pVrxKOgFmlCQYsOGF7pIo5zh6V1GqOnoBZpQts2rcN8tjtY9Ig2aFmv7oLPgz0+tE5j9BTUIikYPjbOxj1HuGbHo2zcc6ThUfCWG3oCHw9e7Ig2aFmvT/7SW+YFeDWt0xgPvY9aJGFRzdjo6S741qSjGNHWmn+tWR/JU1CLJGzvoZPzbspVbsI1EnJJrcU4mx6gSYeCWiRhQaWJRksWC12LUQ+zNB8FtUjCVkVYsmh0hBvngzISH91MFElY0KyKJG7C1Sq7SHZpRC2SsIWWLKIQVdlFkqWgFklBWjfloiy7SHJU+hBpI2mWXWThNKIWaSNpll1k4RTUIm1Gc6Gbj0ofIiIZp6AWEck4BbWISMYpqEVEMk5BLSKScZr1IS1HLx2SVqOglpailw5JK1LpQ1qKXjokrUhBLS1FLx2SVqSglpYS9HIhvXRImpmCWlqKXjokrUg3E6Wl6KVD0ooU1NJy9NIhaTUqfYiIZJxG1NKW9FCMNBNzzkV+0r6+PjcyMhL5eUWiUP1QDEA+Z7yucwkTxSkFt6TCzI465/r89mlELW3H76GYqWnH+eIUoKcZJXsU1NJ2wjz8UnmaMWxQq5QicVJQS9sJWom7WtinGf/z8Am++OQPqRQRNSKXqNUNajNbDXwBuAooAfudc38Ud8dEIjc6BId38XevjvHyZa8D4Ap+wjQddFCiRAc5Soy7FXzq4gBH33Br3VMOHxufE9IVjY7IRWoJM6K+CHzcOfdtM3s9cNTMHnfOPRtz30SiMzoEj9wHU0UMWG4/ubRrCSUAOso/e+0sD+QP8Myb1wK31Dzt3kMn54V0hd4vIlGpO4/aOfcj59y3y3/+Z+A5QMMEaS6Hd8FU+OAs2CRv//4f121XK4z1fhGJSkMPvJjZWuAG4Fs++7aa2YiZjZw5cyaa3olEZWIslmOCwthA7xeRyIS+mWhmy4AvAx91zr1Svd85tx/YD9486sh6KK2pXC9mYgwKV3jbii9DVy/0D8KGgdrHNNquqxcmTjXWx67euk22bVo3b062Ae+/eY3q0xKZUEFtZnm8kP6ic+5gvF2SljerXgxA8dzMvolT3j6YG8LVxzTa7vr3wfEvhS9/5AtewNehl0BJEuo+mWhmBvwZcM4599EwJ9WTiVLTg2+tP7rtWg0fe6b+MY206x+cM4p/7WKJzsnz82Z9FJdezdLbd/mP1kVistgnEzcCvw6cMLOny9s+4Zz7WlQdlDYTpl5c3SbomEbabRiYE76XoQdVpDnUDWrn3N/hld1EohGmXlxdHw46poF2QaGsYJas02tOJXn9g14NOEDRdfLUtffWP8avjhzQ7qlr72XnwROMny/imHl6cPjY+MKvQyQhCmpJ3oYB2LwPulZTwniptIxzbhklZ4yVVrB96jf56LPXBR4D5v3cvG9+HTmg3UefvU6rk0vT0rs+JBXD0xvZ+9o+xl/1n4VhPg+SVI45/WqRVZcX2Da9ji1+B1fVogFOf+lR3+/R04PSDBTUkji/90FXq36QpPqYRl98FPQiJj09KM1ApQ9JnN/7oGfzWzXc75hGShdanVyamUbUkrha5YaegClyQceELV3owRRpZgpqSVxQGaKnu8ATO/zfVhdF6UJT8aRZqfQhiVtIGUKlC2lnGlFL4hZShlDpQtqZViEXEcmAWu/6UOlDRCTjFNQiIhmnoBYRyTjdTEyJXq8pImEpqFOw2MehRaS9qPSRgsU+Di0i7UVBnYLFPg4tIu1FQZ2CoMee9SY3EfGjoE6BHocWkUboZmIKFvs4tGaMiLQXBXVKFvomN80YEWk/Kn00Gc0YEWk/CuomoxkjIu1HpY8ULaTWrLX/RNqPRtQpqdSax88XcczUmoePjdc8rtEZI8PHxtm45wjX7HiUjXuO1D2/iGSPgjolC601b7mhh913raenu4DhLV+1+671viPxhf4yEJFsUekjJUE15fHzRYaPjddd7STMDI9avww0Q0SkeWhEnZJaNeWoRr268SjSGhTUKfGrNVdENd1Oj6qLtAYFdUoqteYgUYx69ai6SGtQUKdoyw099NQZ9S5m1kYjNx5FJLu0CnnKqh8JB2/UWxltB+1T2Iq0Fq1CnmG1Rr16XFxEQNPzMiFoup1mbYgIhBhRm9nnzOxFM3smiQ7JDM3aEBEIV/r4PHBbzP0QH5q1ISIQovThnPumma2NvyttZnQIHtsOxXPlDQY46FoN/YOwYcCbFXLqq6z+9l5+xp3hRVvJqRu38fbcK/DgLpgYg67eS+0Dv+fwrLbX/SJ87+vhjhWRTAg166Mc1F91zr21RputwFaANWvW3PTCCy9E1MUWNDoED38Epif99+cLsHmf9+dH7oOpWTXpjjyYzT220r46cEeH5h8f9F0Ka5FU1Zr1EVlQz6bpeXU8+FaYOFW7Tddq72e9drPbf6zqNkKY7wEuFK7mVvdZLe0lkqJaQa1ZH2mYGIumTb32Ic9RuPAj/tL9FqsuO8vpCyv49F/fDdwTHNbV5RSVT0RipXnUaejqDdcmTLta5wx5vAN6O87SYd7PXbafpx/d79+4Uk6ZOOUdOXHK+zw6FL6vItKQMNPz/gL4B2CdmY2Z2Yfj71aL6x+EXGfw/nzBa9M/6P15to78/GMr7f2+p+r46kpXyUGHzd221Cb5zck/9+/b4V3za95TRW+7iMQizKyPf59ER9pKpUxQZ9bHJdVlBr9tfqWHyrZy2x+zgkPT19Pf8TSr7CVOuytZZWd9u7iq4yXf7W5iDGtgu4gsnt710Ub83ivyxGX30eMT1hcKV7N0+3fnbf/xJ/8FV3Fm/nZWctUnn4+2wyJtRO/6EMD/vSKnb7qfi7nL57S7mLucpbf7lzJ2T/4qF9zc0ssF18nuyV+Nq9sibU+zPtrM/PeK3AJrr5hTSllSYxbHyBtuZccrcP+SoUvlk09dHODoG25N5gJE2pCCWrxQDjm9btumdew8OMlXJt95aVshn2O3HmsXiY2CWhpSGY3vPXRSD8iIJERBLQ0Luwq6iERDNxNFRDJOQS0iknEKahGRjFNQi4hknIJaRCTjFNQiIhmnoBYRyTgFtYhIximoRUQyTkEtIpJxCmoRkYxTUIuIZJyCWkQk4xTUIiIZp6AWEck4BbWISMYpqEVEMq7pV3gZPjauZaFEpKU1dVAPHxtn58ETFKemARg/X2TnwRMAsYa1fjmISJKauvSx99DJSyFdUZyaZu+hk7F9Z+WXw/j5Io6ZXw7Dx8Zj+04RaW9NHdSnzxcb2h6FNH45iEh7a+qgXtVdaGh7FNL45SAi7a2pg3rbpnUU8rk52wr5HNs2rYvtO4N+CXSYqfwhIrFo6qDeckMPu+9aT093AQN6ugvsvmt9rDf2/H45AEw7p1q1iMSiqWd9gBfWSc64qHzXx4eOM+3cnH2VWrVmgIhIlJo+qNOw/uldnOwcIkfp0rZxt4JPXRzgkfPvnGk4OgSHd8HEGHT1Qv8gbBhIocci0swU1A36/v/4D/zcPz2E2dztvXaWPfkDLM93Au+F0SEuPnwvS6Zf9RpMnPI+g8JaRBoSqkZtZreZ2Ukze97MdsTdqcUYPjbOxj1HuGbHo2zcc2RBNeNa5/jZF4bmhXTFUpvk/vxfAnDhscGZkC5bMv0qFx4bbLg/ItLe6o6ozSwHfAa4FRgDnjKzrzjnno27c42K4knFeufIuRIEBDXA0uKPAbi8/LNa0HYRkSBhSh/vAJ53zv0AwMweAu4Eog3q0SF4bDsUz81sKyyH2x+oXSqYVQe+mRXscNfT3/k0q+wsp8t1472HOkMH9d5DJ7l1+m+5v3OIHjvLNB10UOLFh1dC7g+Ytg6WzKpNz9PVC8Dp0pX0dpydt/t06Up6Q/VERMQTpvTRA5ya9XmsvG0OM9tqZiNmNnLmzJnGejE6BMP3zA1p8D4P3+PtDzrukftg4hTguIozfDD3v+ntOEuHQW+HVzfue+Xx0F3pe+Vx9uQP0NtxFjNYYiU6DK7iDDxyHy9d+Q6qJnvMyBe8G4bAgc4PcMF1ztl9wXVyoPMDofsiIgLhgtrvf/TnRZVzbr9zrs8517dy5crGenF4F5Sm/PeVprz9QcdNzX0isLp+vNQm2dn5V6G7srPzr1hqk/47p4q88eI4P1h7NxfpwDnvX4QD6FoNm/ddGv2/7b1bGXRbGSutoOSMsdIKBt1W3vberaH7IiIC4UofY8DqWZ97gdOR9mJibGH76x1X9kbmlyAW3HZijGs/9qfAn9Zs5pVa7uHXDvXrLXsisihhgvop4DozuwYYB+4G3hdpL7p6y+WLGvsXclyZBR0f1HYhffGR9MM4ItKa6pY+nHMXgd8BDgHPAUPOue9E2ov+QSaZ/1g24G3vD5jS1j/o1YVrmVU3DtuXwHM2ei4RkQiEmkftnPuac+7nnXPXOuf+a+S92DDA8Rt3c84t8+q+5X/OuWUcv3F38KyPDQNeXbhrNWDez74Pz/08q24cti+VczrgIh2UHPyYlTy1/vf1sIqIJC4zTyaOr76D3zp2DeeL3k3FK5bm+b3Nb6lfOtgwEH14bhhgeHrjnPnUAIWncuxePa5yhogkKhNvz6s8ZFIJaYBXp2rMVU6AFggQkazIRFBnMRS1QICIZEUmgjqLoZjG6jEiIn4yEdRZXDUljdVjRET8ZCKos7hqShqrx4iI+MnErI+srpqiB1ZEJAsyMaIGLxRLAW870g08EWlnmQlq0A08ERE/mQpq3cATEZkvEzXqiko9eO+hk3rjnIhIWaaCGnQDT0SkWqZKHyIiMp+CWkQk4xTUIiIZp6AWEck4BbWISMaZC3gacFEnNTsDvBCy+QpoYPXZ1tGO192O1wy67naz0Ov+WefcSr8dsQR1I8xsxDnXl2onUtCO192O1wy67rT7kbQ4rlulDxGRjFNQi4hkXBaCen/aHUhJO153O14z6LrbTeTXnXqNWkREasvCiFpERGpQUIuIZFxiQW1mt5nZSTN73sx2+Ow3M9tX3j9qZjcm1be4hLjm95evddTM/t7Mrk+jn1Grd92z2r3dzKbN7FeS7F9cwly3mb3LzJ42s++Y2d8m3ceohfhvvMvMHjGz4+Vr/lAa/YyamX3OzF40s2cC9kebZ8652P8BcsD3gZ8DOoHjwJur2rwHeAww4GbgW0n0LeVr/tfAFeU/397s1xz2ume1OwJ8DfiVtPud0N93N/AssKb8+WfS7ncC1/wJ4IHyn1cC54DOtPsewbX/W+BG4JmA/ZHmWVIj6ncAzzvnfuCcmwQeAu6sanMn8AXneRLoNrOrE+pfHOpes3Pu751zL5c/Pgn0JtzHOIT5uwa4F/gy8GKSnYtRmOt+H3DQOfdDAOdcs197mGt2wOvNzIBleEF9MdluRs859028awkSaZ4lFdQ9wKlZn8fK2xpt00wavZ4P4/0GbnZ1r9vMeoBfBv4kwX7FLczf988DV5jZN8zsqJl9MLHexSPMNf834F8Cp4ETwO8650rJdC9VkeZZUiu8mM+26nmBYdo0k9DXY2bvxgvqd8bao2SEue5PA9udc9PeQKslhLnuJcBNQD9QAP7BzJ50zv3fuDsXkzDXvAl4GrgFuBZ43Mz+j3Pulbg7l7JI8yypoB4DVs/63Iv3G7bRNs0k1PWY2QbgAHC7c+6lhPoWpzDX3Qc8VA7pFcB7zOyic244mS7GIux/42edcz8Ffmpm3wSuB5o1qMNc84eAPc4r3D5vZv8PeBPwj8l0MTWR5llSpY+ngOvM7Boz6wTuBr5S1eYrwAfLd0tvBiaccz9KqH9xqHvNZrYGOAj8ehOPqqrVvW7n3DXOubXOubXA/wTuafKQhnD/jT8M/BszW2JmS4F/BTyXcD+jFOaaf4j3fxCY2RuBdcAPEu1lOiLNs0RG1M65i2b2O8AhvDvFn3POfcfMfru8/0/w7v6/B3geuID3m7hphbzmQeBK4LPl0eVF1+RvGwt53S0nzHU7554zs/8FjAIl4IBzznd6VzMI+Xf9X4DPm9kJvHLAdudc07/61Mz+AngXsMLMxoDfA/IQT57pEXIRkYzTk4kiIhmnoBYRyTgFtYhIximoRUQyTkEtIpJxCmoRkYxTUIuIZNz/B38JLCrLMn9PAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#预测\n",
    "pred = np.empty(N)\n",
    "for i in range(N):\n",
    "    pred[i] = root(data[i])\n",
    "\n",
    "draw(pred)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
